######################################
############python笔记#########

# ###eval(x)  将字符串x转化为对应类型（去除引号，自动变为引号内类型）
# a="{1:'a',2:'b',3:'c'}"
# print(type(a))
# b=eval(a)
# print(type(b))

# while(1):
#     a=input("请输入:")
#     print('a:',type(a))
#     b=eval(a)
#     print('b:',type(b))


# str1 = "这是一个变量"
# print("变量str1的值是："+str1)
# print("变量str1的地址是：%d" %(id(str1)))
# str2 = str1
# print("变量str2的值是："+str2)
# print("变量str2的地址是：%d" %(id(str2)))
# str1 = "这是另一个变量"
# print("变量str1的值是："+str1)
# print("变量str1的地址是：%d" %(id(str1)))
# print("变量str2的值是："+str2)
# print("变量str2的地址是：%d" %(id(str2)))

# x =3
# x += 3
# print(x)
# x -= 3
# print(x)
# x *= 3
# print(x)
# x /= 3
# print(x)

# print("%d %d %d"%(1,2,3))
# print("%d %d %d"%(1.1,2.5,3.6))
# print("%e %e %e"%(1.1,2.5,3.6))
# print("%f %f %f"%(1.1,2.5,3.6))
# print("%5.2f %5.3f %6.7f"%(1.1,2.5,3.6))
# print("%10.2f %5.3f %6.7f"%(12345.12345,2.5,3.6))

# height=float(input('请输入小明身高：'))
# weight=float(input('请输入小明体重：'))
# BMI=weight/(height**2)
# if BMI<18.5:
#     print('过轻')
# elif 18.5<=BMI<25:
#     print('正常')
# elif 25<=BMI<28:
#     print('过重')
# elif 28<=BMI<32:
#     print('肥胖')
# else:
#     print('严重肥胖')

# aDict={"apple":1,"orange":2,"banana":3,"watermelon":4}
# aStr=input("请输入：")
# if aDict.get(aStr)!=None:
#     print(aDict.get(aStr))
# else:
#     print("not found!")

# x = input('Please input a list:')
# x = eval(x)
# start, end = eval(input('Please input the start position and the end position:'))
# print(x[start:end+1])



# import heapq
# import itertools
# import time
#
# class EightPuzzle:
#     def __init__(self, state, parent=None, action=None, cost=0):
#         self.state = state
#         self.parent = parent
#         self.action = action
#         self.cost = cost
#         self.g = cost  # 实际代价（从初始状态到当前状态）
#         self.h = self.heuristic()  # 估计代价（从当前状态到目标状态）
#         self.f = self.g + self.h  # 总代价
#
#     def heuristic(self, heuristic_type='combined'):
#         """
#         计算启发式值。
#         :param heuristic_type: 'combined' 使用汉明距离和曼哈顿距离的线性组合，'manhattan' 仅使用曼哈顿距离。
#         :return: 启发式值。
#         """
#         if heuristic_type == 'combined':
#             return self.hamming_distance() + self.manhattan_distance()
#         elif heuristic_type == 'manhattan':
#             return self.manhattan_distance()
#         else:
#             raise ValueError("Unknown heuristic type")
#
#     def hamming_distance(self):
#         """
#         计算汉明距离（当前状态与目标状态不同数字的数量）。
#         :return: 汉明距离。
#         """
#         target = [int(digit) for digit in '123456780']
#         return sum(1 for x, y in zip(self.state, target) if x != y and x != 0)
#
#     def manhattan_distance(self):
#         """
#         计算曼哈顿距离（空格和目标数字移动所需的步数之和）。
#         :return: 曼哈顿距离。
#         """
#         zero_index = self.state.index(0)
#         zero_row, zero_col = divmod(zero_index, 3)
#
#         distance = 0
#         for i, digit in enumerate(self.state):
#             if digit != 0:
#                 target_row, target_col = divmod((int(digit) - 1), 3)
#                 distance += abs(zero_row - target_row) + abs(zero_col - target_col)
#
#         return distance
#
#     def is_goal(self, goal_state):
#         """
#         检查当前状态是否为目标状态。
#         :param goal_state: 目标状态。
#         :return: 是否为目标状态。
#         """
#         return self.state == goal_state
#
#     def get_neighbors(self):
#         """
#         获取当前状态的所有邻居状态（通过移动空格得到的）。
#         :return: 邻居状态的列表。
#         """
#         zero_index = self.state.index(0)
#         row, col = divmod(zero_index, 3)
#
#         moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右移动
#         neighbors = []
#
#         for move in moves:
#             new_row, new_col = row + move[0], col + move[1]
#
#             if 0 <= new_row < 3 and 0 <= new_col < 3:
#                 new_index = new_row * 3 + new_col
#                 new_state = list(self.state)
#                 new_state[zero_index], new_state[new_index] = new_state[new_index], new_state[zero_index]
#
#                 neighbors.append(EightPuzzle(new_state, self, move, self.cost + 1))
#
#         return neighbors
#
#     def __lt__(self, other):
#         """
#         用于优先队列的比较操作（根据f值）。
#         :param other: 另一个状态。
#         :return: 比较结果。
#         """
#         return self.f < other.f
#
# def a_star_search(initial_state, goal_state, heuristic_type='combined'):
#     """
#     使用A*算法搜索8数码问题的解。
#     :param initial_state: 初始状态。
#     :param goal_state: 目标状态。
#     :param heuristic_type: 启发式类型（'combined' 或 'manhattan'）。
#     :return: 解的路径、扩展节点数和生成节点数。
#     """
#     initial_node = EightPuzzle(initial_state, None, None, 0)
#     open_set = []
#     heapq.heappush(open_set, initial_node)
#     closed_set = set()
#
#     expanded_nodes = 0
#     generated_nodes = 1  # 初始节点已生成
#
#     while open_set:
#         current_node = heapq.heappop(open_set)
#
#         if current_node.is_goal(goal_state):
#             path = []
#             while current_node:
#                 path.append((current_node.state, current_node.action))
#                 current_node = current_node.parent
#             return path[::-1], expanded_nodes, generated_nodes
#
#         closed_set.add(tuple(current_node.state))
#         expanded_nodes += 1
#
#         for neighbor in current_node.get_neighbors():
#             if tuple(neighbor.state) not in closed_set:
#                 heapq.heappush(open_set, neighbor)
#                 generated_nodes += 1
#
#     return None, expanded_nodes, generated_nodes  # 未找到解
#
# def breadth_first_search(initial_state, goal_state):
#     """
#     使用宽度优先搜索算法搜索8数码问题的解。
#     :param initial_state: 初始状态。
#     :param goal_state: 目标状态。
#     :return: 解的路径、扩展节点数和生成节点数。
#     """
#     initial_node = EightPuzzle(initial_state, None, None, 0)
#     queue = [initial_node]
#     closed_set = set()
#
#     expanded_nodes = 0
#     generated_nodes = 1  # 初始节点已生成
#
#     while queue:
#         current_node = queue.pop(0)
#
#         if current_node.is_goal(goal_state):
#             path = []
#             while current_node:
#                 path.append((current_node.state, current_node.action))
#                 current_node = current_node.parent
#             return path[::-1], expanded_nodes, generated_nodes
#
#         closed_set.add(tuple(current_node.state))
#         expanded_nodes += 1
#
#         for neighbor in current_node.get_neighbors():
#             if tuple(neighbor.state) not in closed_set:
#                 queue.append(neighbor)
#                 generated_nodes += 1
#
#     return None, expanded_nodes, generated_nodes  # 未找到解
#
# # 示例使用
# if __name__ == "__main__":
#     initial_state = [4, 1, 7, 2, 0, 8, 6, 3, 5]  # 示例初始状态
#     goal_state = [1, 2, 3, 8, 0, 4, 7, 6, 5]  # 示例目标状态
#
#     # A*搜索（汉明+曼哈顿）
#     start_time = time.time()
#     solution_combined, expanded_nodes_combined, generated_nodes_combined = a_star_search(initial_state, goal_state, 'combined')
#     end_time = time.time()
#     runtime_combined = end_time - start_time
#
#     # A*搜索（曼哈顿）
#     start_time = time.time()
#     solution_manhattan, expanded_nodes_manhattan, generated_nodes_manhattan = a_star_search(initial_state, goal_state, 'manhattan')
#     end_time = time.time()
#     runtime_manhattan = end_time - start_time
#
#     # 宽度优先搜索
#     start_time = time.time()
#     solution_bfs, expanded_nodes_bfs, generated_nodes_bfs = breadth_first_search(initial_state, goal_state)
#     end_time = time.time()
#     runtime_bfs = end_time - start_time
#
#     # 输出结果
#     print("Combined Heuristic:")
#     print("Solution:", solution_combined)
#     print("Expanded Nodes:", expanded_nodes_combined)
#     print("Generated Nodes:", generated_nodes_combined)
#     print("Runtime:", runtime_combined)